#include <iostream>
#include <vector>
#include <ctype.h>

using namespace std;

/**
 * @brief The Solution class 784. 字母大小写全排列
 */
class Solution {
public:
    Solution():ret(),path(),n(0)
    {

    }
public:
    vector<string> letterCasePermutation(const string& s) {
        n = s.size();

        dfs(s,0);
        return ret;
    }

private:
    vector<string> ret;
    vector<char> path;
    int n;
private:
    void dfs(const string& s, int i)
    {
        if(i == n)
        {
            string str;
            for(const char ch: path)
            {
                str+=ch;
            }
            ret.push_back(str);
            return;
        }


        char ch = s[i];
        path.push_back(ch);
        dfs(s,i+1);
        path.pop_back();


        if(std::isupper(ch))
        {
            ch = std::tolower(ch);
            path.push_back(ch);
            dfs(s,i+1);
            path.pop_back();
        }
        else if(std::islower(ch))
        {
            ch = std::toupper(ch);
            path.push_back(ch);
            dfs(s,i+1);
            path.pop_back();
        }

    }
};


//int main()
//{
//    cout << "Hello World!" << endl;
//    Solution solution;

//    cout << "End" << ret.size() << endl;
//}
